package com.datastructures2.graph.无向图;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;

/**
 * 广度优先搜索
 * @author MaoLin Wang
 * @date 2020/2/2116:12
 */
public class BreadthFirstPaths {
    private final int start;
    private int[] edgeTo;
    private boolean[] marked;

    public BreadthFirstPaths(Graph graph,int start) {
        this.start = start;
        edgeTo=new int[graph.V()];
        marked=new boolean[graph.V()];
        bfs(graph,start);
    }

    private void bfs(Graph graph, int start) {
       Queue<Integer>queue=new Queue<>();
       queue.enqueue(start);
       marked[start]=true;
        System.out.println(start);
       while (!queue.isEmpty()){
           int v = queue.dequeue();
           for (int w:graph.adj(v)){
               if (!marked[w]){
                   queue.enqueue(w);
                   edgeTo[w]=v;
                   marked[w]=true;
                   System.out.println(w);
               }
           }
       }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Stack<Integer> paths=new Stack<>();
        for (int i = v; i !=start ; i=edgeTo[i]) {
            paths.push(i);
        }
        paths.push(start);
        return paths;
    }

    public static void main(String[] args) {
        Graph graph=new Graph(6);
        graph.addEdge(0,2);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(2,4);
        graph.addEdge(3,5);
        graph.addEdge(3,4);
        BreadthFirstPaths dfs=new BreadthFirstPaths(graph,0);
        Iterable<Integer> paths = dfs.pathTo(0);
        for (Integer i:paths){
            System.out.println(i.toString());
        }
    }
}
